import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/30 20:20
 * @description 二分查找，用于寻找类似的第n个小的数
 */
public class Solution2 {
    public static void main(String[] args) {
        Solution2 solution2 = new Solution2();
        int n = solution2.findKthNumber(3, 3, 5);
    }

    public int findKthNumber(int m, int n, int k) {
        int lo = 1, hi = m * n;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (!enough(m, n, mid, k)) {
                lo = mid + 1;
            }else {
                hi = mid;
            }
        }
        return lo;
    }
    public boolean enough(int m, int n, int mid, int k) {
        // 统计小于等于mid的数在乘法表中的个数，每一行有多少个，最多有n个
        int cnt = 0;
        for(int i = 1; i <= m; i++) {
            // mid / i 代表小于mid的整数有多少个
            cnt += Math.min(n, mid / i);
        }
        return cnt >= k;
    }
}
